Graph Theory
Q32.
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?Q33.
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,f):1\leqi\leq12, 1\leqj\leq12}. There is an edge between (a,b) and (c,d) if |a-c|\leq1 and |b-d| \leq1. The number of edges in the graph is ____.Q35.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?Q37.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.Q38.
The conic section that is obtained when a right circular cone is cut through a plane that is parallel to the side of the cone is called _____Q40.
An ordered n-tuple (d_{1}, d_{2} ,... , d_{n}) with d_{1}\geq d_{2} \geq ... \geq d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2} ,... , d_{n} respectively. Which of the following 6-tuples is NOT graphic?